Рис. 5.2. Пример криптоарифметической задачи: каждая буква обозначает отдельную цифру; задание состоит в том, чтобы найти такую замену букв цифрами, чтобы результирующее выражение суммирования было арифметически правильным, с дополнительным ограничением, что наличие ведущих нулей не допускается (а); гиперграф ограничений для этой криптоарифметической задачи, на котором показано ограничение Alldif f, а также ограничения сложения по столбцам; каждое ограничение обозначено квадратом, который соединен с ограничиваемыми им переменными (б)

Все ограничения, рассматривавшиеся до сих пор, были абсолютными ограничениями, нарушение которых равносильно тому, что какое-то потенциальное решение больше не рассматривается как таковое. С другой стороны, во многих реальных задачах CSP применяются ограничения предпочтения, которые указывают, какие решения являются предпочтительными. Например, в задаче составления расписания занятий в университете может потребоваться учесть, что профессор х предпочитает проводить занятия по утрам, а профессор У— после полудня. Расписание занятий, в котором предусмотрено проведение профессором х занятия в 14:00, все еще может рассматриваться как решение (если не окажется, что профессор X должен в это время председательствовать на заседании кафедры), но уже не будет оптимальным. Ограничения предпочтения часто можно закодировать как стоимости присваиваний отдельных переменных; например, за назначение профессору X послеполуденного интервала придется заплатить 2 пункта, которые будут учтены в суммарном значении целевой функции, в то время как утренний интервал имеет стоимость 1 пункт. При использовании такой формулировки задачи CSP с предпочтениями можно решать, используя методы поиска с оптимизацией, либо основанные на поиске пути, либо локальные. Подобные задачи CSP в данной главе больше не рассматриваются, но в разделе с библиографическими заметками приведены некоторые ссылки.